// 决策树树结点
class DeNode{
  constructor(node){
    this.node = node;

    this.len = 0
    this.Ct = 0 
    this.flag = 0
    this.node_name_ = ''
    this.cmd =''
    this.width = 0
  }

  // 获取KD树深度
  getDepth(){
    this.depth = 1;
    this.updateDepth(this.node, 1);
    return this.depth;
  }
  
  updateDepth(node, lv){
    if(Object.keys(node).length == 1) return;
    this.depth = Math.max(this.depth, lv);
    for(var key in node){
      if(key!='node'){
        this.updateDepth(node[key], lv+1);
      }
    }
  }

  getWidth(){
    this.width = 0;
    this.updateWidth(this.node)
    return this.width;
  }

  updateWidth(node){
    if(Object.keys(node).length == 1) this.width++;
    for(var key in node){
      if(key!='node'){
        this.updateWidth(node[key]);
      }
    }
  }

  purn(data=[], label=[], flag=0, tree=this.node){
    var new_tree = Object.assign({}, tree);
    this.flag = flag;
    this.getDepth();
    this.node_name_ = ''
    this.node_name = ''
    this.cmd =''
    this.treepurning(tree, data, label);
    if(this.cmd.length>0 && this.node_name_.length>0 && this.node_name.length>0)
    {
      var cmd_ = "delete " + this.cmd
      eval(cmd_)
      var str_ = this.cmd + " = {'node' : '" + this.node_name_ + "'}" 
      eval(str_)
    }
    return new_tree
  }

  treepurning(tree={}, data=[], label=[], depth=1, str_pre=''){
    let that = this;
    var depth_ = depth
    var str = str_pre
    for(var key in tree){
      if(key != 'node'){
        if(Object.keys(tree[key]).length == 1){
          if(depth_ == that.depth && that.flag == 0){
            that.flag++;
            that.node_name = tree['node'];
            var N = []
            var node_name = []
            for(var key_ in tree){
              if(key_!='node'){
                var index=0
                for(var i=0;i<label.length;i++){
                  if(tree['node']==label[i]){
                    index=i
                    break
                  }
                }
                var data_=[]
                for(var j=0;j<data.length;j++){
                  if(data[j][index]==key_){
                    data_.push(data[j])
                  }
                }
                N.push(data_.length)
                node_name.push(tree[key_]['node'])
              }
            }
  
            var max_index = 0
            var max_n = 0
            for(var k=0;k<N.length;k++){
              if(N[k]>max_n){
                max_n = N[k]
                max_index = k
              }
            }
            that.node_name_ = node_name[max_index] 
            that.cmd = str
            break
          }
          else {
            that.node_name_ = '' 
            that.cmd = ''
          }
        }
        else{
          depth_++
          var index=0
          for(var i=0;i<label.length;i++){
            if(tree['node']==label[i]){
              index=i
              break
            }
          }
          var data_=[]
          for(var j=0;j<data.length;j++){
            if(data[j][index]==key){
              data_.push(data[j])
            }
          }
          if(str.length==0){
            str += "new_tree['" + key + "']" 
          }
          else{
            str+="['" + key + "']" 
          }
          that.treepurning(tree[key], data_, label, depth_, str)
        }
      }
    }
  }

  cal_cost(data, label, alpha=1, tree=this.node){
    let that = this
    that.len = 0
    that.Ct = 0
    that.cal_cost_(tree , data, label)
    that.getWidth();
    var Cat = that.Ct + that.width * alpha;
    return Cat
  }
  
  cal_cost_(tree, data, label){
    let that = this
    var node = tree['node']
    for(var key in tree){
      if(Object.keys(tree).length == 1)
      {
        //找到有几类
        var know = [],know_num = []
        console.log(data);
        if(data.length == 0){
          know_num = [0]
        }
        else{
          know_num = [1]
          know.push(data[0][data[0].length-1])
          for(var i=1;i<data.length;i++){
            var unknown = 0
            for(var j=0;j<know.length;j++){
              if(data[i][data[i].length-1]==know[j]){
                unknown = 0
                know_num[j]++
                break
              }
              else{
                unknown = 1
              }
            }
            if(unknown==1){
              know.push(data[i][data[i].length])
              know_num.push(1)
            }
          }
          var Ctk=0
          for(var z=0;z<know_num.length;z++){
            Ctk+=know_num[z]*(Math.LOG2E*Math.log(know_num[z]/data.length))
          }
          that.Ct += -Ctk
        }
        
        //计算损失函数
        // var know_index=[]
        // for(var k=0;k<know.length;k++)
        // {
        //   know_index[k]=0
        // }
        // for(var x=0;x<know_index.length;x++){
        //   for(var y=0;y<data.length;y++){
        //     if(data[y].toString()==know[x].toString())
        //     {
        //       know_index[x]++
        //     }
        //   }
        // }
        
        break
      }
      if(key!='node'){
        var data_ = []
        var index = 0
        for(var i=0;i<label.length;i++){
          if(label[i]==node){
            index = i
            break
          }
        }
        for(var j=0;j<data.length;j++){
          if(data[j][index]==key){
            data_.push(data[j])
          }
        }
        that.cal_cost_(tree[key], data_, label)
      }
    }
  }

  cal_child_cost(tree={}, data=[], label=[], depth=0, purn_cmd='', data_last=data){
    var d = depth
    let that = this
    var cmd = purn_cmd
    if(Object.keys(tree).length != 1){
      for(var key in tree){
        if(key != 'node'){
          if(Object.keys(tree[key]).length != 1){
            if(cmd.length==0){
              cmd += "new_tree.node['" + key + "']" 
            }
            else{
              cmd+="['" + key + "']" 
            }
            d++
            var index_last=0
            for(var i=0;i<label.length;i++){
              if(tree['node']==label[i]){
                index_last = i
              }
            }
            var data_last_ =[]
            for(var j=0;j<data_last.length;j++){
              if(data_last[j][index_last]==key){
                data_last_.push(data_last[j])
              }
            }
            that.cal_child_cost(tree[key], data, label, d, cmd, data_last_)
          }
        }
        else if(d>0){
          //找到剪枝结点名 并找到剪枝后的结果
          var key_num = []
          var key_name = []
          console.log(data_last);
          key_name.push(data_last[0][data_last[0].length-1])
          for(var j=0;j<data_last.length;j++){
            var flag_key = 0
            var key_s =''
            for(var k=0;k<key_name.length;k++){
              if(data_last[j][data_last[j].length-1]!=key_name[k]){
                key_s = data_last[j][data_last[j].length-1]
                flag_key = 1
              }
              else{
                flag_key = 0
                break
              }
            }
            if(flag_key){
              key_name.push(key_s)
            }
          }
          for(var x=0;x<key_name.length;x++){
            key_num.push(0)
          }
          for(var y=0;y<key_name.length;y++){
            for(var z=0;z<data_last.length;z++){
              if(data_last[z][data_last[z].length-1]==key_name[y]){
                key_num[y]++
              }
            }
          }

          var max_key = 0
          var max_name = key_name[0]

          for(var s=0;s<key_num.length;s++){
            if(key_num[s]>max_key){
              max_key = key_num[s]
              max_name = key_name[s]
            }
          }

          var Ct = 0
          for(var b=0;b<key_num.length;b++){
            Ct += Math.pow(key_num[b]/data_last.length, 2)
          }
          that.Ctt.push(1-Ct.toFixed(2))
          
          that.cart_cmd.push(purn_cmd)
          that.cart_node_name_.push(max_name)
          that.cart_node_name.push(tree['node'])
        }
      }
    }
  }

  cart_purn(data,label,tree=this.node){
    let that = this

    that.Ctt = []
    that.cart_cmd = []
    that.cart_node_name_ = []
    that.cart_node_name = []
    that.gt = []
    that.gt_name = []
    that.cart_alpha = 999999999999
    this.cal_child_cost(tree,data,label)

    var new_tree = new DeNode(Object.assign({}, tree));
    var cmd = ''
    var str = ''

    for(var i=0;i<that.cart_cmd.length;i++){
      var new_tree_ = {}
      var str_ = "new_tree_ = new DeNode(" + that.cart_cmd[i] +")"
      eval(str_)
      var t_n = new_tree_.getWidth()
      var CT = this.cal_gini(data,label,new_tree_)

      var gt = (that.Ctt[i]-CT)/(t_n - 1)
      that.gt.push(gt)

      var cart_node = ''
      var cart_node_str = "cart_node = that.cart_node_name[i]"
      eval(cart_node_str)

      that.gt_name.push(cart_node)
      if(gt<that.cart_alpha){
        that.cart_alpha = gt
        cmd = that.cart_cmd[i]
        str = that.cart_node_name_[i]
      }
    }
    if(cmd!=''){
      var s = "delete "+ cmd
      var s_ = cmd + " = {'node' : '" + str + "'}"
      eval(s)
      eval(s_)
    }
    return new_tree.node
  }

  cal_gini(data=[], label=[], tree = this.node){
    this.gini = 0
    this.data_num = data.length;
    this.cal_gini_(tree , data, label);
    var gini = this.gini;
    return gini.toFixed(2)
  }
  
  cal_gini_(tree, data=[], label=[]){
    let that = this

    var label_index = 0
    for(var i=0;i<label.length;i++){
      if(label[i]==tree['node']){
        label_index = i;
        break
      }
    }
    for(var key in tree){
      if(key!='node'){
        var data_ = [];
        for(var j=0;j<data.length;j++){
          if(data[j][label_index]==key){
            data_.push(data[j])
          }
        }
        if(Object.keys(tree[key]).length == 1){
          if(data_.length>0){
            var data_f = []
            for(var k=0;k<data_.length;k++){
              if(data_[k][data[k].length-1]==tree[key]['node']){
                data_f.push(data_[k])
              }
            }
            var cons = []
            cons.push(data_f[0][data[0].length-1])
            var cons_num = []
            for(var y=0;y<cons.length;y++){
              var cons_flag = 0
              var cons_ =''
              for(var x=0;x<data_f;x++){
                if(data_f[x][data[x].length-1] != cons[y]){
                  cons_ = data_f[x][data[x].length-1]
                  cons_flag = 1
                }
                else{
                  cons_flag =0
                  break
                }
              }
              if(cons_flag){
                cons.push(cons_)
              }
            }

            for(var z=0;z<cons.length;z++){
              cons_num.push(0)
            }
            for(var ii=0;ii<data_f.length;ii++){
              for(var jj=0;jj<cons.length;jj++){
                if(cons[jj]==data_f[ii][data_f[ii].length-1]){
                  cons_num[jj]++
                  break
                }
              }
            }
            
            var gini = 0
            for(var kk=0;kk<cons_num.length;kk++){
              gini += Math.pow(cons_num[kk]/data_f.length,2)
            }
            that.gini += 1-gini;
          }
          
        }
        else{
          this.cal_gini_(tree[key], data_, label);
        }
      }
    }
  }
  
  copy(node){
    this.node = node
  }
}

function res_err(x,y,di_p){
  var r1 = 0, r2 = 0, avg1 = 0, avg2 = 0
  for(var i=0;i<di_p;i++) avg1+=y[i]
  for(var i=di_p;i<x.length;i++) avg2+=y[i]
  if(avg1!=0) avg1 = avg1/di_p
  if(avg2!=0) avg2 = avg2/(x.length - di_p)
  for(var i=0;i<di_p;i++) r1+=parseFloat((Math.pow(y[i] - avg1, 2)).toFixed(6))
  for(var i=di_p;i<x.length;i++) r2+=parseFloat((Math.pow(y[i] - avg2, 2)).toFixed(6))
  var r_er = r1+r2

  return parseFloat((r_er).toFixed(3))
}

function gen_tree(x,y,max_depth,fx_0=0,tree={},tree_depth=0){
  if(tree_depth<max_depth){
    if(Object.keys(tree).length == 0){
      tree['node'] ='All'
    }
    var index = 0, min = Infinity
    for(var i=0;i<x.length;i++){
      var er = res_err(x,y,i)
      if(er<min){
        min = er
        index = i
      }
    }
    if(index!=0){
      if(tree_depth == max_depth-1){
        tree['<'+`${x[index]}`]={'node':fx_0}
        tree['>='+`${x[index]}`]={'node':fx_0}
      }
      else{
        tree['<'+`${x[index]}`]={'node':'x'+'<'+`${x[index]}`}
        tree['>='+`${x[index]}`]={'node':'x'+'>='+`${x[index]}`}
      }
      let left = tree['<'+`${x[index]}`], right = tree['>='+`${x[index]}`]
      gen_tree(x.slice(0,index),y.slice(0,index),max_depth,fx_0,left,tree_depth+1)
      gen_tree(x.slice(index),y.slice(index),max_depth,fx_0,right,tree_depth+1)
    }
  }

  return tree
}

function update_tree(x,y,tree={},rx=[],fx=[]){
  if(Object.keys(tree).length > 1){
    for(var key in tree){
      if(key!='node'){
        
        if(key.indexOf("<")>=0){
          var str = parseFloat(key.split("<")[1])
          var x_=[],y_=[]
          for(var i=0;i<x.length;i++){
            if(x[i]<str){
              x_.push(x[i])
              y_.push(y[i])
            }
          }
          update_tree(x_,y_,tree[key],rx,fx)
        }
        else{
          var str = parseFloat(key.split(">=")[1])
          var x_=[],y_=[]
          for(var i=0;i<x.length;i++){
            if(x[i]>=str){
              x_.push(x[i])
              y_.push(y[i])
            }
          }
          update_tree(x_,y_,tree[key],rx,fx)
        }
        
      }
    }
  }
  else{
    var y_ = tree['node']
    var r = 0
    for(var i=0;i<x.length;i++){
      r += y[i]-y_
    }
    rx.push(parseFloat(r.toFixed(3)))
    tree['node'] = parseFloat((parseFloat(y_.toFixed(2)) + 0.1*parseFloat(r.toFixed(2))).toFixed(3))
    fx.push(parseFloat((parseFloat(y_.toFixed(2)) + 0.1*parseFloat(r.toFixed(2))).toFixed(3)))
  }

  return {'a':tree,'b':rx,'c':fx}
}

export {DeNode,gen_tree,res_err,update_tree};